package week_05;

import java.util.Arrays;

/**
 * 1122. 数组的相对排序
 * 给你两个数组，arr1 和 arr2，
 * <p>
 * arr2 中的元素各不相同
 * arr2 中的每个元素都出现在 arr1 中
 * 对 arr1 中的元素进行排序，
 * 使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。
 * 未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。
 * 示例：
 * <p>
 * 输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
 * 输出：[2,2,2,1,4,3,3,9,6,7,19]
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/relative-sort-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class RelativeSortArray_1122 {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        int n = arr1.length;
        // 使用记数排序
        // 0 <= arr1[i], arr2[i] <= 1000
        int[] count = new int[1000 + 1];
        for (int i = 0; i < n; i++) {
            count[arr1[i]] += 1;
        }

        int[] ans = new int[n];
        int index = 0;
        for (int i = 0; i < arr2.length; i++) {
            while (count[arr2[i]] > 0) {
                ans[index] = arr2[i];
                index++;
                count[arr2[i]] -= 1;
            }
        }
        for (int val = 0; val < 1000; val++) {
            while (count[val] > 0) {
                ans[index] = val;
                index++;
                count[val] -= 1;
            }
        }
        return ans;
    }

    // 错误 用array_hash map 无法处理arr2的相对顺序
    public int[] relativeSortArray2(int[] arr1, int[] arr2) {
        int max = arr2[0];
        for (int i = 0; i < arr2.length; i++) {
            max = Math.max(max, arr2[i]);
        }
        int[] key = new int[max];
        for (int i = 0; i < arr2.length; i++) {
            key[arr2[i]] += 1;
        }
        int n = arr1.length;
        int[] ans = new int[n];
        int index = 0;
        for (int i = 0; i < n; i++) {
            if (key[arr1[i]] > 0) {
                ans[index] = arr1[i];
                index++;
            }
        }
        for (int i = 0; i < n; i++) {
            if (key[arr1[i]] == 0) {
                ans[index] = arr1[i];
                index++;
            }
        }

        return ans;
    }

}
